import java.sql.Array;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BinaryTree {
    static class TreeNode{
        private  char val ;
        private TreeNode left ;
        private TreeNode right ;

        public TreeNode(char val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return this.val + " " ;
        }
    }

    public TreeNode createTree() {    //创造一个二叉树
        TreeNode node1 = new TreeNode('A');
        TreeNode node2 = new TreeNode('B');
        TreeNode node3 = new TreeNode('C');
        TreeNode node4 = new TreeNode('D');
        TreeNode node5 = new TreeNode('E');
        TreeNode node6 = new TreeNode('F');
        TreeNode node7 = new TreeNode('G');
        TreeNode node8 = new TreeNode('H');
        node1.left = node2 ;
        node1.right = node3 ;
         node2.left = node4 ;
        node2.right = node5 ;
        node3.left = node6 ;
        node3.right = node7 ;
        node5.right = node8;
        return  node1 ;
    }
    public List<TreeNode> preOrder(TreeNode root){   // 先序遍历
           List<TreeNode> ret = new ArrayList<>();
           if(root == null) return ret ;
           ret.add(root);
           List<TreeNode> leftTree  = preOrder(root.left);
           ret.addAll(leftTree);
           List<TreeNode> rightTree = preOrder(root.right);
           ret.addAll(rightTree);
           return ret ;
    }
    public List<TreeNode>  inOrder(TreeNode root){   // 中序遍历
        List<TreeNode> ret = new ArrayList<>();
        if(root == null) return ret ;
        List<TreeNode> leftTree  = inOrder(root.left);
        ret.addAll(leftTree);
        ret.add(root);
        List<TreeNode> rightTree = inOrder(root.right);
        ret.addAll(rightTree);
        return ret ;
    }
    public List<TreeNode> postOrder(TreeNode root){   //后序遍历
        List<TreeNode> ret = new ArrayList<>();
        if(root == null) return ret ;
        List<TreeNode> leftTree  = postOrder(root.left);
        ret.addAll(leftTree);
        List<TreeNode> rightTree = postOrder(root.right);
        ret.addAll(rightTree);
        ret.add(root);
        return ret ;
    }
    public int nodeSize(TreeNode root){  // 返回树的结点个数
        if(root == null) return 0 ;
        return nodeSize(root.left) + nodeSize(root.right) + 1 ;

    }
    //获取叶子节点个数
    public int getLeafNodeCount(TreeNode root){
        if(root == null) return 0 ;
        if(root.left == null && root.right == null) return 1 ;
         return  getLeafNodeCount(root.left) + getLeafNodeCount(root.right) ;
    }

    //获取第k层的结点个数 ；
    public int getKLeveNodeCount(TreeNode root , int k){
        if(root == null || k < 1 ) return 0 ;
        if(k == 1) return 1 ;
        return getKLeveNodeCount(root.left , k-1) + getKLeveNodeCount(root.right , k- 1) ;
    }

    //获取树的高度
    public int getHigh(TreeNode root){
        if(root == null) return 0 ;
        int leftTreeHigh = getHigh(root.left);
        int rightTreeHigh = getHigh(root.right);
        return leftTreeHigh > rightTreeHigh ? leftTreeHigh + 1 : rightTreeHigh + 1 ;
    }

    //检测值为key的元素是否存在 ；
    public boolean find(TreeNode root , int key){
        if(root == null) return false ;
        if(root.val == key){
            return true ;
        }
        return find(root.left , key) || find(root.right , key) ;
    }


    //返回值为value的元素
    public TreeNode findNode(TreeNode root , int val){
        if(root == null) return  null ;
        if(root.val == val) return root ;
        TreeNode leftTree = findNode(root.left , val) ;
        TreeNode rightTree = findNode(root.right ,val);
        if(leftTree != null) return leftTree ;
        if(rightTree != null ) return rightTree ;
        return null ;
    }

    // 判断两棵树是否相同 。 时间复杂度 Min( m  , n)  假设一颗树m个结点 ，一颗n个
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true ;
        if(p == null || q == null) return false ;

        if(p.val != q.val){
            return false ;
        }
        return isSameTree(p.left , q.left) &&
                isSameTree(p.right , q.right) ;

    }
    // 判断是否 是root 的子树 ；
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null ) return false ;         //为了避免 root为空 ，而下面的left 导致的空指针 ；
        if(isSameTree(root , subRoot)) return true ;

        return isSubtree(root.left ,subRoot) ||
                isSubtree(root.right , subRoot) ;
    }

}









